1. Field
The present invention relates generally to computer graphics and, more specifically, to collision detection of objects in three dimensional (3D) scenes.
2. Description
One goal of 3D computer graphics is to achieve a realistic, interactive experience. As processor performance increases, more processing power becomes available for implementing a variety of graphical techniques that can be executed in real-time to enhance the overall virtual experience for a user. Collision detection is one technique that allows the addition of immersive features to a virtual interactive experience by providing important visual cues about object interactions in a computer-simulated environment.
Collision detection involves determining if objects in a 3D scene are in contact with each other at a given instance in time. In traditional collision detection algorithms, each model representing an object in a scene is tested against all other models in a pair-wise fashion in order to determine if any of them overlap or collide. For a scene containing a large number of complex models, this brute force technique becomes prohibitively time consuming and may be a limiting factor for overall simulation performance.
As a result, collision detection processing in some systems has been divided into two levels. A first level reports potential collisions among all objects in the environment. These results are then sent to a second level, which performs exact collision detection between each pair of objects. In order to minimize invocations of the second level system (that is, to report as few potential object/object collisions as possible), each object is enclosed in a bounding volume and an algorithm is applied to find all bounding volume/bounding volume pairs that overlap.
Despite such improvements in 3D scene processing, better approaches are needed to provide a user with the best possible immersive experience.